// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem76.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=76 lang=cpp
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for(char c : t)
            need[c]++;

        int left = 0;       /* 左窗口 */
        int right = 0;      /* 右窗口 */
        int vaild = 0;      /* 窗口中所含子串数目 */
        int start = 0, len = INT_MAX;       /* 纪录最小覆盖子串的起始索引以及长度 */

        while(right < s.size())
        {
            //此c是将移入窗口的字符
            char c = s[right];

            //右移窗口
            right++;

            //对窗口内数据进行一系列更新
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                    vaild++;
            }

            //判断左侧窗口是否要收缩
            while(vaild == need.size())
            {
                //在这里更新最小覆盖子串
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                //d是将移出窗口的字符
                char d = s[left];
                
                //左移窗口
                left++;

                //进行窗口内数据的一系列更新
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        vaild--;
                    }
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start,len);
    }
};
// @lc code=end

